package com.mystudy.leetcode.problem.sort.p_1122;

/**
 * @program: infoalgorithm
 * @description: 数组的相对排序
 * @author: zhouzhilong
 * @create: 2019-07-31 17:15
 **/

import org.junit.After;
import org.junit.Before;
import org.junit.Test;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * 给你两个数组，arr1 和 arr2，
 * <p>
 * arr2 中的元素各不相同
 * arr2 中的每个元素都出现在 arr1 中
 * 对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
 * <p>
 *  
 * <p>
 * 示例：
 * <p>
 * 输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
 * 输出：[2,2,2,1,4,3,3,9,6,7,19]
 *  
 * <p>
 * 提示：
 * <p>
 * arr1.length, arr2.length <= 1000
 * 0 <= arr1[i], arr2[i] <= 1000
 * arr2 中的元素 arr2[i] 各不相同
 * arr2 中的每个元素 arr2[i] 都出现在 arr1 中
 */
public class Solution {
    private static final Logger LOGGER = LoggerFactory.getLogger(Solution.class);

    long startTime = 0L;
    long endTime = 0L;


    @Before
    public void before() {
        startTime = System.nanoTime();
    }

    @Test
    public void test() {

    }

    @After
    public void after() {
        endTime = System.nanoTime();
        double cost = (endTime - startTime) / 1000000.0;
        LOGGER.debug("cost = [{} ms ]", cost);
    }

    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int max = arr1[0];
        for (int i : arr1) {
            if (i > max) {
                max = i;
            }
        }

        int min = arr1[0];
        for (int i : arr1) {
            if (i < min) {
                min = i;
            }
        }

        int[] eleCount = new int[max - min + 1];
        for (int i = 0; i < arr1.length; i++) {
            eleCount[i-min]++;
        }

        for (int i = 0; i < arr2.length; i++) {
            eleCount[arr2[i]-min]--;
        }

        int min2 = arr2[0];
        for (int i : arr2) {
            if (i < min) {
                min = i;
            }
        }

        int count = 0;
        boolean alr = false;
        for (int i = 0; i < eleCount.length; i++) {
            if(!alr){
                if(i+min == min2){
                    for (int i1 : arr2) {
                        eleCount[count] = i1;
                        count++;
                    }
                    alr = true;
                }else if(i+min >min2){
                    for (int i1 : arr2) {
                        eleCount[count] = i1;
                        count++;
                    }
                    alr = true;
                }
            }
            while(eleCount[i]>0){
                arr1[count] = i+min;
                count++;
            }
        }


        return null;
    }


}
